package main.Q1101_1200;

import java.util.*;

public class Q1101_1110 {
    public static void main(String[] args) {
        System.out.println("Question1101：");
        System.out.println("Question1102：");
        System.out.println("Question1103：");
        System.out.println("Question1104：二叉树寻路");
        System.out.println("Question1105：填充书架");
        System.out.println("Question1106：");
        System.out.println("Question1107：");
        System.out.println("Question1108：");
        System.out.println("Question1109：");
        System.out.println("Question1110：删点成林");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
}

class Question1104 {
    public int process(int label, int row) {
        return (1 << row - 1) + (1 << row) - 1 - label;
    }

    public List<Integer> pathInZigZagTree(int label) {
        int row = 1, rowStart = 1;
        while (rowStart * 2 <= label) {
            row++;
            rowStart *= 2;
        }
        if (row % 2 == 0) label = process(label, row);
        List<Integer> result = new ArrayList<Integer>();
        while (row > 0) {
            if (row % 2 == 0) result.add(process(label, row));
            else result.add(label);
            row--;
            label >>= 1;
        }
        Collections.reverse(result);
        return result;
    }
}

class Question1105 {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int curWidth = 0;
            int max = 0;
            dp[i] = Integer.MAX_VALUE;
            for (int j = i - 1; j >= 0; j--) {
                curWidth += books[j][0];
                if (curWidth > shelfWidth) break;
                max = Math.max(max, books[j][1]);
                dp[i] = Math.min(dp[i], dp[j] + max);
            }
        }
        return dp[n];
    }
}

class Question1110 {
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> toDeleteSet = new HashSet<Integer>();
        for (int val : to_delete) {
            toDeleteSet.add(val);
        }
        List<TreeNode> roots = new ArrayList<TreeNode>();
        process(root, true, toDeleteSet, roots);
        return roots;
    }

    public TreeNode process(TreeNode node, boolean isRoot, Set<Integer> toDeleteSet, List<TreeNode> roots) {
        if (node == null) {
            return null;
        }
        boolean deleted = toDeleteSet.contains(node.val);
        node.left = process(node.left, deleted, toDeleteSet, roots);
        node.right = process(node.right, deleted, toDeleteSet, roots);
        if (deleted) {
            return null;
        } else {
            if (isRoot) {
                roots.add(node);
            }
            return node;
        }
    }
}